package lc20240627;

import java.util.HashMap;
import java.util.Map;

public class MaxPointsInLine {
    public static int maxPoints(int[][] points) {
        int n=points.length;
        int ans=1;
        for (int i = 0; i < n; i++) {
            int[] x=points[i];
            for (int j = i+1; j < n; j++) {
                int[] y=points[j];
                //两点确定一条直线
                int count=2;
                for (int k = j+1; k < n; k++) {
                    int[] z=points[k];
                    int a=(y[0]-x[0])*(z[1]-y[1]);
                    int b=(y[1]-x[1])*(z[0]-y[0]);
                    if (a==b){
                        count++;
                    }
                }
                //更新最大值
                ans=Math.max(ans,count);
            }
        }
        return ans;
    }

    public int maxPoints2(int[][] points) {
        if (points.length < 3) {
            return points.length;
        }

        int max = 0;

        for (int i = 0; i < points.length; i++) {
            Map<String, Integer> slopeMap = new HashMap<>();
            int duplicate = 1;
            int curMax = 0;

            for (int j = 0; j < points.length; j++) {
                if (i == j) {
                    continue;
                }

                int dx = points[j][0] - points[i][0];
                int dy = points[j][1] - points[i][1];

                if (dx == 0 && dy == 0) {
                    duplicate++;
                    continue;
                }

                int gcd = gcd(dx, dy);

                dx /= gcd;
                dy /= gcd;

                // To avoid the issue with negative signs
                if (dx < 0) {
                    dx = -dx;
                    dy = -dy;
                }

                String slope = dy + "/" + dx;
                slopeMap.put(slope, slopeMap.getOrDefault(slope, 0) + 1);
                curMax = Math.max(curMax, slopeMap.get(slope));
            }

            max = Math.max(max, curMax + duplicate);
        }

        return max;
    }

    // Helper function to compute the greatest common divisor (GCD) using Euclidean algorithm
    private int gcd(int a, int b) {
        if (b == 0) {
            return a;
        }
        return gcd(b, a % b);
    }

    public static void main(String[] args) {
        int[][] nums={
                {1,2},
                {2,2},{3,3}
        };
//        System.out.println(maxPoints(nums));
        System.out.println(new MaxPointsInLine().maxPoints2(nums));
    }
}
